﻿using System.Text;

namespace Graph;

public class AdjMatrix : IGraph
{
    private int[,] graph;

    public int V { get; }
    public int E { get; }

    public AdjMatrix(string file)
    {
        StreamReader sr = new StreamReader(file);

        string line = sr.ReadLine();
        string[] str = line.Split(' ');

        V = int.Parse(str[0]);
        E = int.Parse(str[1]);

        //空间复杂度 O（V*V），可优化！
        graph = new int[V, V];

        //建图时间复杂度 O（E）
        for (int i = 0; i < E; i++)
        {
            line = sr.ReadLine();
            str = line.Split(' ');

            int a = int.Parse(str[0]);
            int b = int.Parse(str[1]);

            //无向图
            graph[a, b] = 1;
            graph[b, a] = 1;
        }

        sr.Close();
    }

    //查看两点是否相邻 O（1）
    public bool HasEdge(int a, int b)
    {
        return graph[a, b] == 1;
    }

    //求一个点的相邻顶点集 O（V），可优化！
    public IEnumerable<int> Adj(int a)
    {
        List<int> res = new List<int>();

        for (int b = 0; b < V; b++)
        {
            if (graph[a, b] == 1)
            {
                res.Add(b);
            }
        }

        return res;
    }

    //顶点a的相邻点数 O（1）
    public int Degree(int a)
    {
        return Adj(a).Count();
    }

    //打印图信息，输出邻接矩阵
    public override string ToString()
    {
        StringBuilder sb = new StringBuilder();

        sb.Append($"V = {V}, E={E}\n");
        for (int a = 0; a < V; a++)
        {
            for (int b = 0; b < V; b++)
            {
                sb.Append(graph[a, b] + " ");
            }
            sb.Append('\n');
        }

        return sb.ToString();
    }

    //验证
    static void Main(string[] args)
    {
        IGraph graph = new AdjMatrix("图的存储/g.txt");
        Console.WriteLine(graph);

        Console.WriteLine(graph.HasEdge(0, 1));

        var adjs = graph.Adj(0);
        foreach (var v in adjs)
        {
            Console.Write(v + " ");
        }
        Console.WriteLine();

        Console.WriteLine(graph.Degree(0));

        Console.Read();
    }
}
